home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
HPAVC
/
HPAVC CD-ROM.iso
/
CIS_GAME.ARJ
/
QMATH1.THD
< prev
next >
Wrap
Text File
|
1993-06-25
|
65KB
|
1,498 lines
_____________________ Subj: Point-to-Point 2d Geometry _____________________
Fm: MIKE ROBEL 76446,1444 # 173935
To: Anyone Date: 01-Jun-92 22:25:39
I am working on a program, and I need a line to compute the bearing from my
position to a target where I am at x,y and the target is at x1,y1. I tried
using cotanget times the (x-x1)/(y-y1) but it only gives me a reading in 90
degrees, with a +/- depending on whether or not the position of the other
object is left, right, up, or down. rembering my trig, that makes sense
since i think tangents only go to 90 degrees, but is there any easy way to do
this and get bearings from 0 to 360 degrees.
Right now I am working this in quickbasic.
Mike
...........................................................................
Fm: hercules/Assoc. SysOp 75300,3472 # 173977
To: MIKE ROBEL 76446,1444 (X) Date: 02-Jun-92 00:39:19
Using your notation that you are at [x,y] and the target is at [x1,y1], the
bearing to the target is arc-tangent [(y1-y)/(x1-x)], the result can be
evaluated either in degrees or in radians. (It's ok to use arc-cotangent as
in your example.)
There are 4 cases to check:
a) if (y1-y) and (x1-x) are both positive, then the bearing is between 0 to
90 degrees.
b) if (y1-y) is positive but (x1-x) is negative, the the bearing is between
90 to 180 degrees.
c) if (y1-y) is negative but (x1-x) is positive, then the bearing is between
180 to 270 degrees.
d) if (y1-y) and (x1-x) are both negative, then the bearing is between 270 to
360 degrees.
What this means is that you need to add a multiple of 90 degrees to the angle
that you get from the arc-tangent. The value of the multiple is controlled by
the outcome of the four conditions.
There are probably better ways/algorithms to do this. I'm a lousy programmer.
_____________________ Subj: Point-to-Line 2d Geometry _____________________
Fm: KGliner 70363,3672 # 320438
To: all Date: 25-Mar-93 18:27:32
Given a point at coordinates Px,Py, and a line segment with the endpoints
X1,Y1 and X2,Y2, how does one find the closest distance between the point
and the line segment?
Kevin
...........................................................................
Fm: Hans Peter Rushworth 100031,473 # 320619
To: KGliner 70363,3672 (X) Date: 25-Mar-93 21:50:17
I don't have a formula offhand, but I can tell you how to work it out with a
little algebra on your part. The closest point will be either (X1,Y1) or
(X2,Y2) or the point (Ix,Iy) in between that forms a right angle between the
line from that point to (Px,Py), and the original line segment.
Any point on the line bewteen points (X1,Y1) and (X2,Y2) can be expressed
like this:
Ix = X1 + a*(X2-X1) ---(1)
Iy = Y1 + a*(Y2-Y1) ---(2)
The value "a" is a paramter and will be between 0 and 1. If it is greater
than or equal to 1 then the closest point is (X2,Y2). If it is less than or
equal to zero, then the closest point is (X1,Y1). Thats the trivial solution.
So how do you find "a"? Remember dot product of vectors? The dot product of
two vectors is 0 if the angle between them is 90 degrees. The vectors in
question are: [X2-X1,Y2-Y1] and [Px-Ix,Py-Iy]. The dot product of the vectors
is (X2-X1)*(Px-Ix) + (Y2-Y1)*(Py-Iy) = 0. ---(3)
That is not enough for a solution, since that is true for any point that lies
on the line (PxIx,PyIy). You need to substitute the equations (1),(2) above
for Ix and Iy (which are in terms of the parameter a) into equation (3). If
you solve this you will get a value for a. Now see if a is in the range 0-1
and if so substitute it back into the equations (1) and (2), and this should
give the result. Neat Huh? <g>
Hope that helps (and is right!)
Peter.
...........................................................................
Fm: Hans Peter Rushworth 100031,473 # 320627
To: Hans Peter Rushworth 100031,473 (X) Date: 25-Mar-93 22:03:00
Again I misread the question !
Once you have the point Ix,Iy, it is a simple matter to work out the distance
using the formula:
distance = sqrt((Px-Ix)*(Px-Ix) + (Py-Iy)*(Py-Iy))
Substuting Ix & Iy with X1,Y1 or X2,Y2 if a is not in between 0 and 1.
Peter.
...........................................................................
Fm: Bob Provencher/GD SL 71621,2632 # 320949
To: KGliner 70363,3672 (X) Date: 26-Mar-93 13:45:38
Kevin -
Let's see, if you can't project the point onto the line segment, then the
shortest distance should be the min of the distance to the two end points.
If you can project the point orthogonally onto the line, then the shortest
distance should be the distance to the projection point.
If Pete's method doesn't work out, I'll see if I can work this out.
Bob
...........................................................................
Fm: rod lentz 71163,57 # 338584
To: John Dlugosz [ViewPoint] 70007,4657 Date: 20-Apr-93 23:22:41
>> how the cos (atan ()) helps you find distance?
Ok; pixture in 2d space the two points you want to find the
distance of. Picture a right triangle connected to it, where
the other 2 sides are parallel to the x & y axes, and the
distance you're after is the hypotenuse.
Given the ratio of the non-hypotenuse sides of a right
triangle atan() returns the angle. The two "sides" you use are
the separate distances in the x & y directions.
Do some swapping of x & y, so that your value is always in the
range 0..1, i.e. (minor axis / major axis). Index your table by
(table size * minor axis / major axis).
Now cos() of the angle from the atan() is the ratio of the
length along the major axis to the length of the hypotenuse.
Of course, making a table of cos(atan()) is the fastest way
to go, rather than 2 separate tables.
Hope that was clear enough !
- Rod
...........................................................................
Fm: Vu Truong (Siliconis) 70242,3015 # 369363
To: Lary Myers 76004,1574 (X) Date: 05-Jun-93 01:00:35
I hope this equation helps (its from my calculus book!)
| = Absolute Bar ^ = Raise to the Power of
D= (|ax0+by0+C|)/(sqr(a^2+b^2))
Distance from point (x0,y0) to line (ax+by+c=0).
...........................................................................
Fm: Bob Provencher/GD SL 71621,2632 # 369473
To: Lary Myers 76004,1574 (X) Date: 05-Jun-93 09:30:09
Hi Lary,
If the point normal to the line (that the line segment is part of) intersects
the line segment <whew> then the intersection to the line segment is the
same as the intersection to the line. Otherwise, it would be the closest
end-point. If that's not enough to go on, I'll work out the equations.
Bob
______________________________ Subj: 3d to 2d ______________________________
Fm: KGliner 70363,3672 # 283627
To: all Date: 22-Jan-93 16:18:27
I've been doing some 3d work lately, and I've run into some problems
projecting a point in 3d to a point in 2d. Normally this isn't difficult,
but I'm having trouble accounting for the horizon.
What I've got are the offset coordinates in 3d for the point relative to
the center of the 'view'. I also know the distance to the horizon (ie. where
it collapses to nothing). Without the horizon factored in, I could just take
the x and y coordinates and use those as is. With the horizon, I need to
scale them depending on the depth (the z coord). I tried using a linear
scaling method (eg. if z is 1/2 the horizon, then reduce x and y by 50%).
That produces values that are sometimes close (depending on the distance of
the horizon), but incorrect.
Anyways, my trig is rusty and I've completely forgotten calculus and all
that matrix stuff. Any help on this would be much appreciated.
...........................................................................
Fm: John Burkhard 71044,3263 # 283746
To: KGliner 70363,3672 (X) Date: 22-Jan-93 19:40:37
Scaling isn't all that complicated. You were kind of on the right track. If
you have two points, call the first the eye point, and the second the focal
point, you compute the distance from the eyepoint to the focal point, and use
that in computing the 2d positions of your 3d points. Like:
E = eye point
F = focal point
P = some arbitrary point
|F| = distance between E and F (could be called the focal length)
|P| = distance from E to P
P.x = P.x * |F| / |P|
P.y = P.y * |F| / |P|
The closer you make F to E, the quicker things will shrink as they approach
the horizon, and the farther away F is from E, the slower they shrink as they
approach the horizon. For your application, you know the distance to the
horizon, so you can select your |F| to be such that stuff becomes scaled too
small for display at the desired distance away.
...........................................................................
Fm: John Burkhard 71044,3263 # 285095
To: KGliner 70363,3672 (X) Date: 24-Jan-93 18:27:54
>> How do I remove the distortion when up close to objects in my field of
view? (ie. if I have a string of points that constitute a straight line in
3d, I want to them to retain that straightness in 2d). <<
The method I presented is the same method used when ray tracing. Distortion
is an inevitable artifact of this process. If you want to have a distortion
free scaling, you could try the following: (this one's off the top of my
head, so bear with me...)
Single Point Perspective:
Given H.z, the distance from the focal plane (z=0) to the horizon, the x
and y components of an arbitrary point P will both be proportional to the
distance from the horizon at which P lies.
So:
P'.x = P.x * ( H.z - P.z ) / H.z
P'.y = P.y * ( H.z - P.z ) / H.z
Where:
0 <= P.z <= H.z
When P.z is 0, the point is on the focal plane, and will show at 100% scale.
As P moves closer to H.z, it will be scaled linearly until P.z = H.z, at
which time both the x and y components will map to 0.
Two point and three point perspective are both a little more complex. I
haven't worked out the math on them yet, but it should be an interesting
exercise.
...........................................................................
Fm: KGliner 70363,3672 # 287196
To: all Date: 28-Jan-93 02:57:38
Well, those 3d to 2d projection formulas seem to work pretty well. Now I'm
stuck on what I think is a bug in the rotation-translation portion of my
code.
In a nutshell, I'm trying to translate the 3d global coordinates of a point
to the 3d local coordinate system of the 'viewer'. I've been using a sort of
hacked together arctangent table (using the slope of the line between the two
points) and that works-- to a point (no pun intended). But I'm getting a
slight distortion in my numbers so that when I connect a line between several
points that were linear in the global coordinate system now appear just
barely non-linear in the local coordinate system.
I've been pouring over the Lee Adams books (High Performance CAD graphics in
C and Visualization Graphics in C), but he's got so many variables without
clear explanation it's been difficult for me to pick out the parts I'm
looking for. I did notice that an arctangent call was unnecessary, and that
I had to change my numbers slightly depending on what the angle was (ie. <
90, between 90 and 180, etc-- something I already do). But I got lost after
that.
Any suggestions?
Thanks, Kevin
____________________________ Subj: more 3d to 2d ____________________________
Fm: KGliner 70363,3672 # 287699
To: John Burkhard 71044,3263 Date: 28-Jan-93 23:09:51
John (and Bob)- What I have is are the coordinates (Px,Py,Pz) of a point in
a global 3d coordinate system. I also have the coordinates of the 'viewer',
or camera, from which this point is being viewed (we'll call these
coordinates Vx,Vy,Vz). In addition, I have the global XY, XZ, and YZ angles
that the camera is oriented.
What I want to be able to do is find the coordinates of the point P in the
camera's local 3d coordinate system (where the camera sits at 0,0,0). The
next step is to project it onto a 2d screen, but I've already got that part
working (your earlier formula worked great for that).
The overall goal here is to display a virtual 3d environment from any
location and view within it (something I have already achieved, but not with
the exact precision I want-- hence this question).
Thanks,
Kevin
...........................................................................
Fm: Bob Provencher/GD SL 71621,2632 # 288055
To: KGliner 70363,3672 (X) Date: 29-Jan-93 18:36:26
Hi Kevin -
If you want the co-ordinates of the point (Px,Py,Pz) relative to the viewer
at (Vx,Vy,Vz) then it's (Px-Vx,Py-Vy,Pz-Vz) (call it Rx,Ry,Rz).
Projecting the point onto the viewer screen can be done by scaling...
Assuming +Z is into the screen, +Y is from the bottom to the top, and +X is
from left to right (all co-ordinates are relative to the viewer), and Z1 is
the distance from the viewer to the screen. The the X and Y coordinates of
the point on the screen (relative to the center) are given by:
X = Rx * Z1/Rz
Y = Ry * Z1/Rz
In the same units that X,Y,Z were originally in.
I just came up with all this stuff off of the top of my head, so it may be
completely wrong for all I know <g>.
Bob
...........................................................................
Fm: Bob Provencher/GD SL 71621,2632 # 289651
To: KGliner 70363,3672 (X) Date: 01-Feb-93 12:35:02
Hi Kevin -
Sorry I couldn't remember the 2D matrix rotation stuff off the top of my
head the other day. It's been a little while since I used it.
I'm pulling this stuff straight out of one of my graphics book, in this case
it's "Computer Graphics, A Programming Approach," by Steven Harrington,
McGraw-Hill, 1987, ISBN 0-07-026753-7.
The rotation transformation matrix, R, for rotation counterclockwise
w degrees, about the point ( 0, 0 ) is:
R = | cos w -sin w |
| sin w cos w |
To compute the co-ordinates of a point p = ( x, y ) after rotation, you do
matrix multiplication on the point with R:
p' = | x y | | cos w sin w | = | x cos w + y -sin w x sin w y cos w |
| -sin w cos w |
p' = ( x * cos(w) ) + ( y * -sin(w) ), ( x * sin(w) ) + ( y * cos(w) )
For example, rotating ( 1, 0 ) +90 degrees:
p' = ( 1 * cos(90) ) + ( 0 * -sin(90) ), ( 1 * sin(90) ) + ( 0 * cos(90) )
p' = ( 0 ) + ( 0 ), ( 1 ) + ( 0 )
p' = 0, 1
rotating ( 1, 0 ) 45 degrees:
p' = ( 1 * cos(45) ) + ( 0 * -sin(45) ), ( 1 * sin(45) ) + ( 0 * cos(45) )
p' = ( 0.707 ) + ( 0 ), ( 0.707 ) + ( 0.525 )
p' = 0.707, 0.707
rotating ( 0, 1.414 ) -45 degrees:
p' = ( 0 ) + ( 1.414 * -sin(-45) ), ( 0 ) + ( 1.414 * cos(-45) )
p' = ( 0 ) + ( 1.414 * 0.707 ), ( 0 ) + ( 1.414 * 0.707 )
p' = 1, 1.
If you use a lookup table, it seems to me that the equation for p' can be
computed moderately fast.
Hope this helps
Bob
...........................................................................
Fm: John Burkhard 71044,3263 # 289904
To: KGliner 70363,3672 (X) Date: 01-Feb-93 20:26:50
The mathematics for performing the translate and rotation in 3d are:
Given:
Q is the point to be translated and rotated;
Q' is the result;
T is the translation offset;
r = roll angle;
p = pitch angle;
y = yaw angle;
And
R is the roll rotation matrix
P is the pitch rotation matrix
Y is the yaw rotation matrix
Then:
P' = R * P * Y * (Q-T)
Where:
Q, Q', T are of the form ( x, y, z )
And where:
R = +- -+
| cos r -sin r 0 |
| sin r cos r 0 |
| 0 0 1 |
+- -+
P = +- -+
| 1 0 0 |
| 0 cos p -sin p |
| 0 sin p cos p |
+- -+
Y = +- -+
| cos y 0 -sin y |
| 0 1 0 |
| sin y 0 cos y |
+- -+
The ROLL angle is the angle to rotate about the Z axis;
The PITCH angle is the angle to rotate about the X axis;
And the YAW angle is the angle to rotate about the Y axis.
There are ways to write the above which eliminates floating point math
entirely; only addition, subtraction, multiplication, division and square
root.
HTH,
-jb
________________________ Subj: 3d Rotations _____________________________
( see also the "Flights of Fantasy" thread(s) )
Fm: Mark Betz/GD SL 76605,2346 # 199351
To: Peter Rushworth 100112,1532 (X) Date: 12-Aug-92 23:10:18
We've run into a problem with the translation routines that handle moving the
aircraft through 3 space. The method we're using starts out with an imaginary
point x = 0, y = 0, z = distance travelled. This imaginary point assumes you
have zero rotation relative to the world coordinate system, and are
travelling along the z-axis (straight into the screen in our system). We then
put the point through the following rotations, feeding the results of each
into the next. The dX, dY, and dZ symbols refer to your actual rotation
angles relative to the world axes, not the presumed 0 rotation angle implied
by the imaginary starting point...
Z rotation: X' = (X*COS(dZ)) - (Y*SIN(dZ))
Y' = (X*SIN(dZ)) + (Z*COS(dZ))
Z' = Z
X rotation: X' = X
Y' = (Y*COS(dX)) - (Z*SIN(dX))
Z' = (Y*SIN(dX)) + (Z*COS(dX))
Y rotation: X' = (Z*SIN(dY)) + (X*COS(dY))
Y' = Y
Z' = (Z*COS(dY)) - (X*SIN(dY))
XPos += X'; YPos += Y'; ZPos += Z';
The last three statements translate your position back out to your starting
point, and then add in the new deltas for the three axes.
The problem is that we're getting the right values for change along each
axis, but we're getting the wrong sign for various components, depending on
the rotations. For example. going into this with the view rotated to look NE,
if we feed in values which should cause the plane to move directly forward,
we slide left along a line bisecting the wing, because X is getting smaller
when it should be getting larger. So far the only way I can think of to
correct the problem is to test the rotations going in, and apply some sign
changes based on whatever rules I can discover. I can't help thinking that
we're missing something, though, and that we shouldn't have to flip signs
explicitly. Any ideas or suggestioins you might have would be greatly
appreciated. If it's my turn to initiate the transatlantic phone call say the
word <g>.
--Mark
__________________________ Subj: more 3d Rotations __________________________
Fm: Chris Lampton [GAMPUB] 76711,301 # 371227
To: All Date: 08-Jun-93 00:08:46
Okay, folks, I have a math question. It probably has a simple answer, but the
question itself is rather difficult to express. Here's my best shot:
I have an infinite plane defined in terms of two pieces of information: the
normal of the plane and an arbitrary reference point somewhere on the plane.
The normal is represented as a unit vector -- call it {nx,ny,nz} -- and the
reference point as a set of x,y,z coordinates. (Call these rx,ry,rz.) I also
know the x,y,z coordinates of a second point on the plane. (Call it px,py,pz)
What I want to do is rotate the plane around the reference point into a new
orientation, which would have a normal of {nx',ny',nz'}. (Specifically, I
want to rotate it to {0,0,1}, which would make it parallel to the x,y plane.)
The question is, how do I calculate the rotated coordinates (call them
px',py',pz') of the point at px,py,pz, the second point on the plane? Seems
like this should be easy to do, since the elements of the unit normal vectors
appear to correspond to the sines and cosines of the rotations of the normal
in the x,y, y,z and x,z planes. But I'm not quite sure how to get from one
normal to another, i.e. how to figure the sine and cosine of the _difference_
between the two normals so I can use them to rotate the point from one to the
other. The arccos and arcsin might come in handy -- I could use them to
calculate the angles, then subtract the angles and perform the standard
rotation operations on the point using the difference in the angles -- but I
have a suspicion that there's a simpler way, since I already seem to _have_
the sines and cosines in the unit vectors. Should I subtract {nx,ny,nz} from
{nx',ny',nz'} or vice versa? (This doesn't seem to work.) Take the dot
product of the vectors? (This doesn't either.) Perform some other obscure
vector operation? <g> Any suggestions?
Clear as mud, right? But I'm sure somebody out there will understand what the
heck I'm talking about. Hey, Pete...!
--Chris
...........................................................................
Fm: Hans Peter Rushworth 100031,473 # 372011
To: Chris Lampton [GAMPUB] 76711,301 (X) Date: 08-Jun-93 23:21:15
Chris,
>> What I want to do is rotate the plane around the reference point into a
new orientation, which would have a normal of {nx',ny',nz'}.
This is a three step process
Step 1: Translate the plane 1 so it's reference point is at the origin, Step
2: Rotate to align the normals Step 3: Translate back out to the reference
point
Now combine these three transformations (by matrix multiplication) to get a
single transformation that does everything in one go.
I'll assume steps 1 and 3 are no problem. Doing them allows you to do step 2
more easily. Onto step 2, finding a transform to align the normals...
You could solve this using a standard transformation that rotates about an
arbitrary axis a certain number of degrees. The axis would be defined by the
cross product of the two normal vectors, and the angle is found using the dot
product of the two normal vectors. The transform you can derive using
quaternions. But I'll skip the working and just give you the result:
c@ is cos of the angle, s@ is sine of the angle
and a,b,c are the x,y,z components of the unit length cross product vector
[ (a*a + c@*(1-a*a)) (a*b*(1-c@)-c*s@) (a*c*(1-c@) + b*s@) ]
[ (a*b*(1-c@)) + c*s@) (b*b + c@*(1-b*b)) (b*c*(1-c@) - a*s@) ]
[ (a*c*(1-c@)) - b*s@) (c*b*(1-c@)+a*s@) (c*c + c@*(1-c*c)) ]
This may look complex, but actually there is a pattern and there are several
simplifications, particularly cos(theta) and sin(theta) which can be found
from:
cos(@) = a.b (a,b here are unit length plane normals)
sin(@) = axb/n (n is the unit length vector, normal to a and b)
So no trig is needed!
I have never had the need to use this transform, which is the result of
considerable paper calculation using quaternions, so it's possible there is
an error, and the above result differs in one sign from that published in
F&VD (page 227 2nd Ed), which you should consult for more information.
...........................................................................
Fm: Hans Peter Rushworth 100031,473 # 372040
To: Hans Peter Rushworth 100031,473 (X) Date: 09-Jun-93 00:21:15
I would add that there is probably a *much more direct* way of obtaining the
rotation matrix transform of step 2, but that would require more thought and
scribbling, and take longer to explain.
Also I would caution you that a plane normal and one point only describe a
plane, and not the points on the plane. The procedure I outlined does not
take into consideration any rotation of the planes about the surface normal.
it simply aligns the normals so the planes are parallel. You might have to
perform an intermediate rotation step (step 2.5) to align the planes in some
special way depending on the nature of the problem.
______________________ Subj: Union of >1 Rectangles _________________________
Fm: Lutz Kretzschmar 100023,2006 # 372221
To: all Date: 09-Jun-93 09:17:35
Hi all,
I have a programming problem at the moment and think this is the right place
to ask.
I have a number of rectangles that may, or may not, overlap. I need to reduce
this to a minimum number of non-overlapping rectangles. This is for a sort of a
window manager. I keep track of what window regions need to be updated, and
then blit from a virtual screen that contains the whole screen in its correct
state to the actual display. Unfortunately, it's not feasable to just blit
the whole thing over. So I'm looking for an algorithm that will minimize this
time.
Maybe a scanline-based edge intersection list would be a better algorithm,
does anyone have experience with this? I was thinking that I could maintain a
sorted list of edges per scanline, and eliminate or add edges as they appear
during addition of new rects. Then blit scanline by scanline, using the edges
in the list as boundaries.
...........................................................................
Fm: Mark Betz/Ass't SysOp 76605,2346 # 372715
To: Lutz Kretzschmar 100023,2006 (X) Date: 09-Jun-93 22:07:57
Hi, Lutz. I'm not sure I understand the problem completely, but your message
prompted a few thoughts. First, I'm not sure what you mean by "minimum number
of non-overlapping rectangles". I'm assuming for the moment that you want to
find the smallest rectangle which encompasses the area of the screen which
needs to be redrawn. The ways to do this generally break down into two
categories. The first is tracking the "damage rectangle" dynamically. In
other words, as drawing operations take place on the screen you constantly
compare all four corner coordinates of the affected rect against the current
damage rectangle (start with a rectangle of 0 area in the center of the
screen). Anytime that a coordinate falls outside the current range, the range
is adjusted to encompass it. The second method involves calculating the
damage rectangle at update time, by performing some comparisons against the
rectangles affected by any drawing operations since the last update.
A better way to handle windowing operations, imho, is to make the windows
into proactive objects. There are again two general approaches. The first is
to have each window store a copy of the background it obliterates, so that it
can restore that background when it changes position. The downside of this is
that it cannot know about changes to that background since the background was
captured. A better way is exactly how MS Windows, and most other GUIs, do it,
and that is to make each window responsible for repainting itself on command.
--Mark
__________________________ Subj: Pinball Formulas __________________________
Fm: Diana Gruber/Fastgraph 72000,1642 # 371480
To: Randy @ Safari 71165,3600 (X) Date: 08-Jun-93 12:42:06
Randy,
I don't know *all* the equations by heart! I usually look them up in a
college physics book. But here are some suggestions.
The speed of the ball will be constantly changing according to the force
applied. Change in speed is acceleration, Force comes from three sources: the
springs, friction, and gravity. You can probably ignore friction because it
will be trivial compared to the other two forces.
The equation for acceleration is:
a=f/m
Since you don't know what the mass is, normalize it to 1. Then plug in values
for f until the game 'feels' right.
Velocity is calculated in units of pixels per clock tick. The equation is:
v = v0 + at
Position at any point in time is
x = x0 + v[x]t + 1/2a[x]t^2
y = y0 + v[y]t + 1/2a[y]t^2
The angle you bounce off something is the same as the angle you hit it.
I always thought a pinball machine would be real fun to write. If somebody
writes a good one, let me know, I know a publisher who is looking for one.
Diana
__________________________ Subj: Fixed Point Math __________________________
Fm: KGliner 70363,3672 # 296776
To: all Date: 13-Feb-93 22:29:10
I've been going through my program code and replacing all my floating
point code with 32-bit fixed point (where the upper 16 bits is the part to
the left of the decimal, and the lower 16 bits is to the right), but I've run
into a problem with some of the math. Addition and subtraction are no
problem-- it's just certain circumstances of multiplication and division that
I'm unsure about.
For example, say I have two floating point numbers, x=1111.1111 and y=
2222.2222. If these were stored as 32 bit integers, then doing a calculation
like x * y would create an overflow, and x div y would yield a result of
zero.
So the question is, how do I do this and still maintain the same (or close
enough) precision to the floating point calculations (and in assembly
language as well, since the whole reason for using integers is to optimize
for speed)?
...........................................................................
Fm: Hans Peter Rushworth 100031,473 # 297262
To: KGliner 70363,3672 Date: 14-Feb-93 20:47:24
Assuming you have a 386 or 486...
Multiplication first:
MOV EAX,x
IMUL DWORD PTR y ; 64-bit result in EDX:EAX (32 bit fraction is in EAX)
SHRD EAX,EDX,16 ; reposition binary pt, 32-bit result in EAX (16 bit fract)
Division:
MOV EAX,x ; These two lines load x into EDX:EAX
CDQ ;
SHLD EDX,EAX,16 ; convert 48.16-bit value to 32.32-bit one
SHL EAX,16 ; SHLD does not effect the second operand (EAX) so repeat
IDIV DWORD PTR y ; EAX = EDX:EAX/y (16.16-bit), EDX = EDX:EAX % y
Note: these are *signed* multiplies/divides. precision is maintained.
...........................................................................
Fm: Hans Peter Rushworth 100031,473 # 297700
To: KGliner 70363,3672 (X) Date: 15-Feb-93 15:22:30
Kevin,
>> [Inline assembly kludge needed]
Ok... You didn't hear it from me <g> but:
CDQ: 66 99
SHRD EAX,EDX,16 : 66 0F AC D0 10
SHLD EDX,EAX,16 : 66 0F A4 C2 10
(all in hex)
...........................................................................
Fm: KGliner 70363,3672 # 298005
To: Hans Peter Rushworth 100031,473 (X) Date: 16-Feb-93 01:16:13
Peter- Thanks, that sort of worked. That is, the divisor (in EAX) was
correct, but the remainder (in EDX) wasn't. Perhaps it needs to be shifted
16 bits left? I'll experiment with it and see what happens, although part of
the problem may just be my forcing it into inline.
...........................................................................
Fm: Chris Lampton [GAMPUB] 76711,301 # 298520
To: KGliner 70363,3672 (X) Date: 16-Feb-93 23:25:44
After talking with you on the phone, I think I have a clearer idea where the
problem is. For your purposes, you won't need the value in EDX after the
division is performed. Everything you need will be in EAX, with exactly the
16.16 precision you want. Here's how it works in the code Peter gave you:
When you start out, you have a 32-bit dividend with 16.16 precision, which
we'll say looks like this in hex:
76543210
The first instruction of Peter's code:
MOV EAX,x
gets this value into EAX. Now we need to convert this number into a 64-bit
value with 48.16 precision that spans the EAX (low 32 bits) and EDX (high 32
bits) register. We do this by sign-extending EAX into EDX with the CDQ
(Convert Doubleword to Quadword) instruction:
CDQ ;
Now our number has become
0000000076543210
in EDX:EAX. Before we perform division, however, we have to add 16 bits more
precision to the right of the decimal point, because we're going to lose
those bits during division. We do this by shifting the digits of the 64-bit
number in EDX:EAX 16 bits to the left. For reasons that are more easily
understood if you consult a good 80386 programming manual, this requires
_two_ shift instructions:
SHLD EDX,EAX,16 ; convert 48.16-bit value to 32.32-bit one
SHL EAX,16 ; SHLD does not effect the second operand (EAX) so repeat
Now the number looks like this:
0000765432100000
Finally we perform the division:
IDIV DWORD PTR y ; EAX = EDX:EAX/y (16.16-bit), EDX = EDX:EAX % y
This divides the 64-bit number in EDX:EAX by the 32-bit fixed point number at
y. Because this divisor also has 16.16 precision, the division has the effect
of shifting the decimal point back 16 positions to the right in the quotient,
which puts us back where we started -- with a 32-bit number in the EAX
register that has 16.16 precision. Don't worry about what's in EDX, just use
the number in EAX as your result.
_______________________ Subj: Fixed Point Algorithms _______________________
Fm: Chris Lampton [GAMPUB] 76711,301 # 328647
To: Lutz Kretzschmar 100023,2006 (X) Date: 07-Apr-93 12:01:00
In principle, fixed-point math is quite simple. For speed, however, it's best
done with 16:16 precision on an assembly language level, at least on a 32-bit
chip. The reason for limiting the code to 16:16 is that, otherwise, you'll
have to jump through hoops to keep from shifting bits off the end of a
register (or integer variable) and into oblivion.
Fixed point addition and subtraction are trivial; they work just like integer
addition and subtraction. You just have to be sure that the decimal points
are aligned in the two numbers to be added or subtracted.
Multiplication and division are a bit trickier. Bear in mind that
multiplication shifts your decimal point to the left and division shifts your
decimal point to the right. Thus, you must combine the multiplication or
division with a shift to make sure the decimal point ends up where you want
it. (Despite the term "fixed point," the decimal point actually does a lot of
floating around. You have to _work_ to keep it fixed.) With multiplication,
you perform the shift after the operation. With division, you usually perform
it _before_ the operation. The decimal points in the multiplier and
multiplicand (or divisor and dividend) do not need to be aligned, but you do
need to know where the decimal point is going to end up. Here's a simple
rule: After multiplication, the number of digits following the decimal in the
result will be the number of digits following the decimal in the multiplier
PLUS the number of digits following the decimal in the multiplicand, like
this:
aaaaaaaaaaaa.aaaa
x bbbbbbbbbbbb.bbbb
--------------------
cccccccccccc.cccccccc
Note that this is identical to the long multiplication procedure you learned
in school, decimal placement and all.
After division, the number of digits following the decimal in the result will
be the number of digits following the decimal in the dividend MINUS the
number of digits following the decimal in the divisor, like this:
aaaaaaaaaaaa.aaaa
% bbbbbbbbbbbbbb.bb
-------------------
cccccccc.cc
This is why you must shift to the right _before_ division, so that you don't
lose any digits to the right of the decimal point.
Here's a simple C demonstration of fixed point multiplication with 24:8
precision:
long multiplier,multiplicand,product;
product = multiplier * multiplicand >> 8;
And here's a demonstration of fixed point division:
long divisor,dividend,quotient;
quotient = (dividend << 8) / divisor;
Note that the leftmost eight digits of the result are lost in both cases.
Thus, although the official precision of these fixed point variables is 24:8,
the _effective_ precision is only 8:8 -- and we're using 32-bit _longs_ here!
That's why fixed point is better performed in 80386 assembly language. The
386 32-bit multiplication instruction, while restricted to 32-bit operands,
produces a 64-bit result. Thus, while the leftmost digits may be shifted out
of the EAX register, they are preserved in the EDX register, from whence they
can be shifted back into EAX. And the 386 also allows a 64-bit dividend in
division instructions. Pete Rushworth posted some excellent code a while back
for 386 fixed point. If he doesn't jump in here and post it again, I'll see
if I can dig it out, assuming you're interested in working with 386
assembler. But bear in mind that these routines are still restricted to 16:16
precision. If you really need 32:32 precision, you've got a lot of work ahead
of you, unless you're working on a 64-bit CPU!
--Chris
p.s. Sorry I can't point you toward any books, but I've never been able to
find any that discuss it. I talk about this briefly in my book Flights of
Fantasy, but I don't say anything I haven't told you in this message.
...........................................................................
Fm: Chris Lampton [GAMPUB] 76711,301 # 328660
To: Lutz Kretzschmar 100023,2006 (X) Date: 07-Apr-93 12:22:42
Whoops, in that last message where I refer to shifting RIGHT before division,
change that to shifting LEFT before division. I've always been a bit
dyslexic.... <g>
--Chris
...........................................................................
Fm: KGliner 70363,3672 # 329382
To: Lutz Kretzschmar 100023,2006 Date: 08-Apr-93 18:25:32
Ok, this is straight from my code:
Multiply a * b: Division:
mov ebx,[a] mov eax,[dividend]
mov eax,[b] mov ebx,[divisor]
mul ebx xor edx,edx
shr eax,16 div ebx
shl edx,16 mov ecx,eax
mov dx,ax mov eax,0ffffh
mov [result],edx div ebx
shr eax,16
sal ecx,16
mov cx,ax
mov [result],ecx
Both these work for positive numbers. You might be able to speed up the
multiplication, and I know for sure that the division could be more
efficient. For one thing, there should be a way to do it with only one div
instruction, but I never could get it work that way. If you find a way to
optimize it, let me know.
Oh yeah, Randy (at Safari) helped me hack out the division routine,
although he may not want credit for that<g>. I actually had quite a number
of solutions when I posted a similar question about a month or two ago. This
is the only one I could get to work though.
Kevin
___________________________ Subj: Fractal Terrain ___________________________
Fm: Hans Peter Rushworth 100031,473 # 213126
To: Mark Betz/GD SL 76605,2346 (X) Date: 14-Sep-92 22:52:38
If you use a "plasma" type fractal for generating mountains, you can improve
the "flatness" between the mountains and the sea by cubing the altitudes of
the points and then dividing by a constant value. If the result is too
"craggy" you can flatten the peaks using a square root (or similar) function
in more or less the same way. The problem with this method is determining a
realistic course for rivers, and man-made constructions like roads.
There is also a rule (I think it's called Zipfs (sp?) law) that relates to
the distribution of peak altitudes, that might be worth looking into.
Peter.
...........................................................................
Fm: Mark 'SAM' Baker 100025,444 # 213312
To: Mark Betz/GD SL 76605,2346 (X) Date: 15-Sep-92 14:01:49
Fractals are an excellent method of generating pseudo-random terrain.
Plasma clouds are probably the easiest to use; but their are some algorithms
in either 'The Beauty of Fractals' or 'The Mathematics of Fractals' that are
specific to developing continental map simulacrums. For semi-realistic
random-landscapes, fractals are excellent.
...........................................................................
Fm: John Burkhard 71044,3263 # 281177
To: John W. Ratcliff 70253,3237 (X) Date: 18-Jan-93 17:00:33
Along the lines of fractals... Even with an FPU, computation times for
generating the Mandlebrot set over the range -2,-2 .. 2,2 is *very* time
consuming, especially at the resolution you're talking about.
A couple of years ago, when I got hooked on fractals, a friend of mine
suggested an interesting approach to plotting the set. Given that the
points within the set are relatively uninteresting (and take the longest
amount of time to compute), his approach concentrated on the points outside
the set first, and then tackled the points within the set.
He repeatedly subdivided the screen area into four equal sized windows, and
calculated the Mandlebrot function for the center point in each sub region.
If the point calculated was within the set, he added that region to a queue
for later processing; otherwise, he recursively subsidived each of the sub
regions, and so on until the region was 1 pixel big. Once the function
backed all the way out, he grabbed the next region from the queue and
continued.
In pseudo code:
add entire_screen_region to region_queue
while region_queue is not empty
process_region with head of region queue
endwhile
process_region::
if region is 1 pixel big
computer mandlebrot value
plot the appropriate color based upon result
return to caller
else
subdivide region into 4 quadrants
for each quadrant
compute mandlebrot of center point
if result is within the mandlebrot set
add quadrant to region_queue
return to caller
else
fill region with appropriate color, based upon result
process_region with quadrant
endif
next
endif
At least I think that's pretty much how it went. One interesting side note
about the above: While it does result in some extra computations, for the
most part it's not that bad. And since the colored areas are filled in
first, and since there's almost constant screen activity, it *appears* to be
faster than the brute force method of scanning line by line.
-jb
...........................................................................
Fm: Chris Lampton [GAMPUB] 76711,301 # 330470
To: Ralph Wirthlin 76247,715 (X) Date: 10-Apr-93 12:12:14
I fiddled around with some code for generating fractal scenery objects while
writing FLIGHTS OF FANTASY, but didn't include the code in the book because
of technical problems involved in translating the fractal data to the data
format I used for storing objects. (I do discuss it in theory, however, with
a simple demonstration program.) Actually, there are probably an infinite
number of ways to generate fractal landscapes, most of which I've never
attempted (and probably haven't imagined). Most, however, are based on the
same premise: Start with a simple shape and break it recursively into
segments (breaking the segments into segments and so forth, until you've
reached the desired recursive depth). Use a small (or not so small, depending
how "rough" you want to the landscape to look) random factor to perturb, or
"skew", each subsegment from the orientation of the main segment. For
instance, a coastline (or river or highway) could start out as a straight
line, be broken into two skewed segments (not _exactly_ in the middle), which
would each in turn be broken recursively into two skewed segments, and so
forth, until sufficient "crookedness" has been achieved. By using the same
random number seed each time, the coastline can be made reproducible, so that
it will always look the same when the viewer returns to it. This can be done
either in real time (if your code is fast enough) or to generate static data
that can be stored in the scenery database (if you have room for it).
The method that I was tinkering with in FOF (but wound up not using) would
have generated fractal mountains. The basic technique is this: Start out with
a pyramid, i.e. a mountain made out of four triangles with a rectangular
base. Break each triangle into four smaller triangles, like this:
*
* *
* *
* *
* *
* *
* * * * * * * * * * * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
Note that this involves splitting each edge of the original triangle into two
edges. This should be done with a random factor so that the break rarely
occurs at the exact center of an edge and the break points should be randomly
perturbed from the original line by a few units in the x and/or y directions
to make the new edges slightly (or not-so-slightly) skewed. This gives the
divided triangle a jagged, rocky look (which it does not have in my simple
ASCII illustration). Then repeat this process recursively on all four smaller
triangles, until you have as much detail as you need (or can handle). Do this
with each triangular face of the original pyramid and you have a mountain.
(One of the trickiest parts is making sure that all the mountain faces meet
at common vertices.) Obviously you don't start drawing (or storing) any of
this until you reach the lowest level of recursion; intermediate data should
be discarded.
I realize this is a somewhat simplistic explanation of fractal scenery
generation, and probably doesn't begin to answer the questions that you have,
but it establishes the principles. I plan to research this topic in greater
detail (because I still have a lot of questions about it too). I'll let you
know what I find.
--Chris
...........................................................................
Fm: Chris Lampton [GAMPUB] 76711,301 # 330906
To: Mitchell Waite 75146,3515 (X) Date: 10-Apr-93 22:51:28
As a matter of fact, there's been a lot of serious talk around here about how
COMANCHE: MAXIMUM OVERKILL works. The present technique does _not_ seem to
use fractals. I'm not really giving away any secrets (at least among this
crowd) if I tell you that the NovaLogic programmers maintain a 2-dimensional
integer array representing the terrain, where each element of the array
represents the height of the corresponding piece of terrain above some fixed
level. (Additional information, such as terrain color, may also be contained
in the array elements.) They then apparently use a technique known as
raycasting (a kind of highly simplified raytracing) to establish how these
height fields would appear from the viewer's position. This is hard to
explain, but...imagine that the viewport on the display is divided from left
to right into vertical columns one pixel in width, each stretching from the
top to the bottom of the viewport. (There would be 320 such columns in a
full-screen mode 13h viewport.) A single ray (basically, a straight line) is
"cast" from the viewer's position for each of these vertical columns. Each
time the ray passes over a terrain element (which the COMANCHE developers
apparently refer to as "voxels," though that's not how that term is
traditionally used), a vertical segment of the current screen column
representing the (rotated and perspective-projected) difference in height
between that voxel and the previous voxel passed over by the ray is painted
in the (light-sourced?) voxel color. Magically, this gives the appearance of
a three-dimensional landscape. If you look closely at the COMANCHE screen,
you'll see that it appears to be made out of vertically elongated pixels,
which change their elongation as you move relative to the terrain.
That's a pretty rough sketch of the technique, of course. It's a very clever
-- and very fast -- method of drawing hyper-realistic terrain. The main
problem at present is that the terrain array requires a lot of storage,
limiting the terrain size and resolution. However, if someone found a way to
combine it with fractal terrain generation techniques, it might be possible
to generate nearly infinite amounts of high-resolution, stunningly-realistic
terrain. I'm itching for a chance to experiment with these techniques and see
if I can get them to work. And I'd love to write a book (or part of a book)
about the results.
I've played with the FRACTINT plasma fractals a bit, with some very
interesting results. Wonder if there's a way to get _that_ sort_ of thing
working in real time? It's a completely different technique than that used in
COMANCHE, but probably more versatile and with more long-range possibilities.
--Chris
...........................................................................
Fm: John Dlugosz [ViewPoint] 70007,4657 # 330491
To: Ralph Wirthlin 76247,715 (X) Date: 10-Apr-93 12:28:01
Well, here is a simple example. It uses midpoint subdivision of triangles.
void z (pair p, pair p1, pair p2, int n)
{
if (A[p.x][p.y] != 0) return; //already covered this one
fpnum val= A[p1.x][p1.y] + A[p2.x][p2.y];
val += random (n);
A[p.x][p.y]= val/2;
// show what is happening
plot (p);
}
/* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
void compute (pair p, int n)
{
const half_n= n/2;
pair right= point (p.x+n, p.y);
pair down= point (p.x, p.y+n);
//find midpoints
int midx= p.x+half_n;
int midy= p.y+half_n;
pair pr= point (midx, p.y);
pair pd= point (p.x, midy);
pair rd= point (midx, midy);
// find z values
z (pr, p,right, n);
z (pd, p,down, n);
z (rd, right,down, n);
if (n != 1 && n != -1) {
compute (p, half_n);
compute (pr, half_n);
compute (pd, half_n);
compute (rd, -half_n);
}
}
/* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */
int main (int argc, char* argv[])
{
if (argc > 1) seed= atol(argv[1]);
setup_A();
activate (d);
setup_d();
show_scale();
compute (point(0,0), 128);
compute (point(128,128), -128);
saveimage();
key::get();
return 0;
}
________________________ Subj: Random Bit Generator ________________________
Fm: Serge Mathieu 71035,2771 # 250051
To: Mark Betz/Ass't SysOp 76605,2346 (X) Date: 23-Nov-92 22:22:45
Mark,
I'm not sure if this is the right way to code it in asm...
_PSEUDO-RANDOM SEQUENCE GENERATOR FOR 32-BIT CPUs_ by Bruce Schneier (DrDOBBS
Journal)
int RANDOM () {
static unsigned long register; /*Register must be unsigned so right
shift works properly.*/
/*Register should be initialized with some random value.*/
register = ((((register >> 31) /*Shift the 32nd bit to the first bit*/
^ (register >> 6) /*XOR it with the seventh bit*/
^ (register >> 4) /*XOR it with the fifth bit*/
^ (register >> 2) /*XOR it with the third bit*/
^ (register >> 1) /*XOR it with the second bit*/
^ register) /*and XOR it with the first bit.*/
& 0x0000001) /*Strip all the other bits off and*/
<<31) /*move it back to the 32nd bit.*/
| (register >> 1); /*Or with the register shifted right.*/
return register & 0x00000001; /*Return the first bit.*/ }
BASM (TP6 built-in asm, 286 code) (note:bits 1 to 32) for 2 x 16 bit
registers:
Seed in DX:AX cl contains number of bits to generate ch is random
number (maximum 8 bits) bx used to xor bit 32 with bits 7,5,3,2,1
mov cl,number_of_bits_needed
xor ch,ch
@Bit_Loop:
mov bh,dh {bit 32}
mov bl,al {bits 7,5,3,2,1}
shl bl,1 {bit 7 to upper bit}
xor bh,bl {xor upper bits and don't care about others}
shl bl,2 {bit 5}
xor bh,bl
shl bl,2 {bit 3}
xor bh,bl
shl bl,1 {bit 2}
xor bh,bl
shl bl,1 {bit 1}
xor bh,bl
shr dx,1 {shift seed 16 bits}
rcr ax,1 {plus 16 bits for 32 bits}
rcl ch,1 {ch builds random number from bit 1}
and bh,10000000b {bit 8}
or dh,bh {to update bit 32}
dec cl
jnz @Bit_Loop
Serge Mathieu
...........................................................................
Fm: Hans Peter Rushworth 100031,473 # 206819
To: Sarwan Narine 76675,164 (X) Date: 31-Aug-92 11:40:45
The most common and fast method is the "Linear Congruential Generator":
X(n+1) = ((a*X(n))+c) mod m. where a,c,m are specially chosen constants.
Knuth gives an in-depth analysis of this complex topic in "Seminumerical
Algorithms".
Another method that is useful for binary decision making purposes (ie random
YES/NO decisions), is based on data scrambling and encryption schemes. These
methods employ a shift register with the output data element being the
exclusive or of selected bits in the register. The output data bit is fed
back into the input of the register, and each clock produces a pseudo random
bit. The choice of which bits to feedback and the initial value of the
register is important in order to produce a long non-repeating sequence. Most
Communications Theory textbooks describe this method when applied to
Peter.
________________________ Subj: Point inside polygon? ________________________
Fm: Tim Koffley 70334,16 # 379820
To: all Date: 20-Jun-93 12:39:18
Ok geometry fans, anyone got a quick/easy algorithm for determining if a
point is inside a *strictly convex* polygon? I'm translating a board game to
Windows (via Visual Basic) and I'm trying to detect when the mouse moves over
a "room" on the board. The rooms are n-vertex convex polygons. I'm looking
for something quick (and possibly dirty) as the sucker is called anytime the
mouse moves (and it *is* Basic).
Thanks in advance,
-tk
...........................................................................
Fm: Patrick Reilly 71333,2764 # 380001
To: Tim Koffley 70334,16 (X) Date: 20-Jun-93 16:59:01
Tim,
All I can think of is to walk through the line segments that make up the
polygon and find all that intersect the x coord of the point and the y coord
of the point; if you end up with at least 4, with at least one above, one
below, one left and one right, its in the polygon.
-Pat-
...........................................................................
Fm: Tim Koffley 70334,16 # 380078
To: Patrick Reilly 71333,2764 (X) Date: 20-Jun-93 18:21:26
>All I can think of is to walk through the line segments that make up the
polygon and find all >that intersect the x coord of the point and the y coord
of the point; if you end up with at least >4, with at least one above, one
below, one left and one right, its in the polygon.
I kinda understand what you're saying. But...
a) what about triangular rooms
b) I'm not sure what you mean by "above, below, left, right" and how you
determine a segment's "aboveness" or otherwise...
If you feel like it, walk me through this case.....
|\
| \
| \ o <----- the point in question
| \
| \
------------
If that works, show with the point inside.
thanks,
-tk
...........................................................................
Fm: Patrick Reilly 71333,2764 # 380415
To: Tim Koffley 70334,16 Date: 21-Jun-93 01:16:47
Tim,
For your triangle (or any other n-gon with vertices >= 3):
|\
| \
| X o <----- the point in question
| X
| \
-------X----
The "X" indicates where a line segment from the triangle is intersected by
the x, and y, coordinates of the point. It has 1 "X" to its left, and two
"X"s below - the point is not contained within the triangle.
|\
| X
X o X <----- the point in question
| \
| \
---X--------
There is now an X in each direction from the point (one left, one right, one
above and one below) - the point is contained in the triangle.
|\
| \
X o <----- the point in question
| \
| \
-----X------
The point IS one of the intersections - you have to decide whether it should
be considered within or without the triangle.
This will work with any convex 2D polygon. Algorithm:
Let point = X,Y.
Let N be the number of vertices in the polygon.
Left left = top = right = bottom = False.
For each vertex V in the polygon do
Let VN be the next vertex from V (VN of V(N-1) is V(0))
<special case>
If VN.x == V.x and VN.x == X then
If (VN.y <= Y and V.y >= Y) or (VN.y >= Y and V.y <= Y) then
<lies on a vertical line - immediately pass or fail>
<special case>
Else If VN.y == V.y and VN.y == Y then
If (VN.x <= X and V.x >= X) or (VN.x >= X and V.x <= X) then
<lies on a horizontal line - immediately pass or fail>
<line is neither vertical nor horizontal>
Else
r = (X-V.x)*(VN.y-V.y)/(VN.x-V.x) + V.y
If r < Y then Top = True;
Else if r > Y then Bottom = True
Else <pass/fail - point lies on the line>
r = (Y-V.y)*(VN.x-V.x)/(VN.y-V.y) + V.x
If r < X then Left = True
Else If r > X then Right = True
Else <pass/fail - point lies on the line>
If Top = True and Bottom = True and Left = True and Right = True
Pass.
Else
Fail.
-Pat-
...........................................................................
Fm: Chris Lampton [GAMPUB] 76711,301 # 380007
To: Tim Koffley 70334,16 (X) Date: 20-Jun-93 17:07:55
Here's a quote from Alan Watt's FUNDAMENTALS OF THREE-DIMENSIONAL computer
graphics: "The sum of the angles between lines drawn from the point to each
vertex is 360 degrees if the point is inside the polygon, but not if the
point lies outside."
That sounds like a lot of work to put yourself and your program through,
especially if the code is to be executed every time the mouse moves. The
quickest and dirtiest alternative I can think of would trade off a big chunk
of memory for speed: Set aside a byte array (or the closest VB equivalent) in
which each element corresponds to a pixel location on the game board and
contains the number of the room of which that pixel is part (or a value
indicating that it's not part of a room). For the cost of an array index, you
can know whether the mouse is inside a room and which room it is inside.
--Chris
...........................................................................
Fm: Tim Koffley 70334,16 # 380079
To: Chris Lampton [GAMPUB] 76711,301 (X) Date: 20-Jun-93 18:21:32
>graphics: "The sum of the angles between lines drawn from the point to each
vertex is 360 >degrees if the point is inside the polygon, but not if the
point lies outside."
Thanks for the info. Of course, I *knew* about that property of a convex
polygon, I just...er....FORGOT OK? <g>. That might not be *too* bad cuz
most rooms are either 4 or 5 vertices and I've split the board into four
regions to narrow/speed the search a bit. *Plus* I now realize I can
discount positions of a certain color (talk about digging!).
>can think of would trade off a big chunk of memory for speed: Set aside a
byte array in which >each element corresponds to a pixel location on the game
board
Your alternate idea is fine BUT, I'm trying to keep with Windows' silly
measurement system of "twips" for other practical reasons and, besides, my
board bit map is roughly 1000x800 pixels!
-tk
...........................................................................
Fm: Chris Lampton [GAMPUB] 76711,301 # 380099
To: Tim Koffley 70334,16 (X) Date: 20-Jun-93 19:02:28
>my board bit map is roughly 1000x800 pixels!
Hey, that would only be a 782 kilobyte array! Cheap at the price! <g>
Heck, if you can use pixel color to trivially dismiss positions -- use it!
The ideal would be to use a different interior palette for every polygon, so
that the board bitmap itself could be used to easily differentiate polygons.
Of course, that's a bit of a kludge, but I'm always on the lookout for a
useful kludge. ;-)
--Chris
...........................................................................
Fm: Jez San @ Argonaut 72247,3661 # 380148
To: Tim Koffley 70334,16 (X) Date: 20-Jun-93 19:48:40
tk -
use a bounding rectangle that totally contains your polygon to do trivial
checking to see which area of the screen the mouse pointer is in, ie: to
within 1 or 2 possible polygons.
Then you can do a simple plane equation check for each edge of the polygon to
ensure that the point of the mouse pointer is on the correct side of each
plane (ie: checking that the normal to the plane always points away from the
point, or something similar).
-- Jez.
...........................................................................
Fm: David Laturner 100031,1127 # 380461
To: Tim Koffley 70334,16 Date: 21-Jun-93 06:03:45
How about a sparse array?
For each pixel row in the game board, store the columns where rooms start
and end ( or vice versa ). Then your check will be a simple linear search
along the row the mouse is in.
Dave.
...........................................................................
Fm: Tim Koffley 70334,16 # 381110
To: Patrick Reilly 71333,2764 (X) Date: 21-Jun-93 22:32:01
Thank a lot for the reply. I now understand what you're talking about. I'm
currently trying the "Total interior angles from the point = 360" method.
It's ok for now but I might have to try something different later. Thanks
again!
-tk
...........................................................................
Fm: Tim Koffley 70334,16 # 381117
To: David Laturner 100031,1127 (X) Date: 21-Jun-93 22:33:38
>For each pixel row in the game board, store the columns where rooms start
and end ( or vice >versa ). Then your check will be a simple linear search
along the row the mouse is in.
Another fine idea! Thanks...
-tk
...........................................................................
